# 解决散列冲突的方法： 开散列（将冲突的元素放在主表之外，拉链法），闭散列（放在主表之中，常见的如线性探测法，线性探测法会造成元素堆积，影响算法性能）
# 对于线性探测法，装填因子最好不要超过0.7
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class ChainHashTable:
    def __init__(self, size):
        self.size = size
        self.hash_table = [None] * size

    def __hash(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.__hash(key)
        if self.hash_table[index] is None:
            self.hash_table[index] = Node(key, value)
        else:
            current = self.hash_table[index]
            while current.next is not None:
                current = current.next
            current.next = Node(key, value)

    def search(self, key):
        index = self.__hash(key)
        current = self.hash_table[index]
        while current is not None:
            if current.key == key:
                return current.value
            current = current.next
        return None
